# -*- coding: utf-8 -*-
"""
Spyder Editor

This is a temporary script file.
"""
import pandas as pd
import copy
def process_data(s1,s2):
    df1=pd.read_csv(s1)
    df2=pd.read_csv(s2)
    edge=df1.loc[:,['SourceNodeID','DNodeID','Edgecapactiy','Edgetravaltime']].values
    node=df2.loc[:,['NodeID','Occupancy','Nodecapacity']].values
    node_number=len(node)
    graph=[]
    edge_capacity=[]
    node_capacity=[]
    for i in range(node_number+1):
        t1=[2**31-1]*(node_number+1)
        graph.append(t1)
        t2=[0]*(node_number+1)
        edge_capacity.append(t2)
        node_capacity.append(0)
    for i in range(node_number+1):
        graph[i][i]=0
    for i in range(len(edge)):
        graph[edge[i][0]][edge[i][1]]=edge[i][3]
        graph[edge[i][1]][edge[i][0]]=edge[i][3]
        edge_capacity[edge[i][0]][edge[i][1]]=edge[i][2]
        edge_capacity[edge[i][1]][edge[i][0]]=edge[i][2]
    for i in range(1,node_number+1):
        node_capacity[i]=node[i-1][2]
    people_number=0
    target=[]

    for i in range(1,node_number+1):
        if node[i-1][1]>0:
            edge_capacity[0][i]=node[i-1][1]
            graph[0][i]=0
            people_number+=node[i-1][1]
        if node[i-1][1]<0:
            target.append(i)

    node_capacity[0]=people_number
    return graph,edge_capacity,node_capacity,target


def dijkstra(num,start,target,visited,global_edge_capacity,global_node_capacity,t):
    dis=num[start]
    visited[start]=1
    father=[0]*len(num)
    flag=0
    while start not in target:
        last_start=start
        max_num=2**31-1
        for i in range(len(num)):
            #print(dis[i],t)
            #print(global_node_capacity[after_t][i])
            if visited[i]==0 and dis[i]<max_num:
                #if global_node_capacity[t+dis[last_start]][i]>0 and global_edge_capacity[t+dis[last_start]][last_start][i]>0:
                max_num=dis[i]
                start=i
                
        if start==last_start:
            flag=1
            break
        visited[start]=1
        dis[start]=max_num
        for i in range(len(num)):
            if visited[i]==0 and dis[i]>dis[start]+num[start][i]:
                dis[i]=dis[start]+num[start][i]
                father[i]=start
    if flag==1:
        return -1,-1,-1
    end=start
    return dis,father,end
def get_road(start,end,father):
    road=[]
    while start!=end:
        road.append(end)
        end=father[end]
    road.append(start)
    road=road[::-1]
    return road
def change_global(dis,global_edge_capacity,global_node_capacity,t,road,min_capacity):
    time=dis
    for i in range(len(road)-1):
        global_node_capacity[t+time[road[i]]][road[i]]=global_node_capacity[t+time[road[i]]][road[i]]-min_capacity
    for tt in range(t+time[road[i]],1000):
        global_node_capacity[tt][road[-1]]=global_node_capacity[tt][road[-1]]-min_capacity
    for tt in range(t+time[road[0]],1000):
            global_edge_capacity[tt][road[0]][road[1]]=global_edge_capacity[tt][road[0]][road[1]]-min_capacity
    for i in range(1,len(road)-1):
        for tt in range(t+time[road[i]],t+time[road[i+1]],1):
            global_edge_capacity[tt][road[i]][road[i+1]]=global_edge_capacity[tt][road[i]][road[i+1]]-min_capacity
    return global_edge_capacity,global_node_capacity

    
def core(target,graph,global_edge_capacity,global_node_capacity,t,result):
    road=None
    while 1:#为了找到所有的最短路，采用死循环
        edge_capacity,node_capacity=global_edge_capacity[t],global_node_capacity[t]
        if node_capacity[0]<=0:#如果虚拟点0 里面的容量，也就是带疏散人数小于等于0了，就可以跳出循环了
            break
        visited=[0]*len(node_capacity)
        #print(global_node_capacity[t])
        '''
        for i in range(len(node_capacity)):
            if node_capacity[i]==0:
                visited[i]=1
        
        for i in range(len(edge_capacity)):
            for j in range(len(edge_capacity[0])):
                if edge_capacity[i][j]==0 and i!=j:
                    graph[i][j]=2**31-1#这里将所有容量为0的节点和边断开，不参与下面的最短路寻找
        '''
        for j in range(len(edge_capacity[0])):
                if edge_capacity[0][j]==0 and 0!=j:
                    graph[0][j]=2**31-1#这里将所有容量为0的节点和边断开，不参与下面的最短路寻找
        
        if road!=None:
            #visited[road[0]]=1
            
            for i in range(1,len(road)):
                visited[road[i]]=1
            
            for i in range(len(road)-1):
                graph[road[i]][road[i+1]]=2**31-1
                graph[road[i+1]][road[i]]=2**31-1
        
        
        dis,father,end=dijkstra(graph,0,target,copy.deepcopy(visited),global_edge_capacity,global_node_capacity,t)#dijkstra找最短路
        
        if end==-1:
            break
        road=get_road(0,end,father)#找到的最短路存放在road里面

        min_capacity=2**31-1
        for i in range(len(road)-1):
           # print('node=',i,' ',node_capacity[i])
            if global_node_capacity[t+dis[road[i]]][road[i]]<min_capacity:
                min_capacity=global_node_capacity[t+dis[road[i]]][road[i]]
        for i in range(len(road)-1):
           # print('edge',road[i],road[i+1],' ',edge_capacity[road[i]][road[i+1]])
            if global_edge_capacity[t+dis[road[i]]][road[i]][road[i+1]]<min_capacity:
                min_capacity=global_edge_capacity[t+dis[road[i]]][road[i]][road[i+1]]#一路遍历最短路，找到节点和边的最小值，即应疏散的人数
        if min_capacity==0:
            break
        ########有每个点的到达时间输出##############

        tt=[]
        for i in range(1,len(road)):
            tt.append((road[i],t+dis[road[i]]))#把经过的节点和节点到达时间输出
        print('路径',tt,'目前剩余人数',node_capacity[0],'将要疏散人数',min_capacity)
        with open("test.txt","a") as f:
            f.write('路径')
            for (i,j) in tt:
                f.write('(')
                f.write(str(i))
                f.write(' ')
                f.write(str(j))
                f.write(')')
            f.write('目前剩余人数')
            f.write(str(node_capacity[0]))
            f.write('将要疏散人数')
            f.write(str(min_capacity))
            f.write('\n') 
        
        ##########只有最终到达时间的输出################
        #print('路径',road,'目前剩余人数',node_capacity[0],'将要疏散人数',min_capacity)
        
        global_edge_capacity,global_node_capacity=\
        change_global(dis,global_edge_capacity,global_node_capacity,t,road,min_capacity)#修改会被影响到的时刻的节点和边的容量
            
    return global_edge_capacity,global_node_capacity

            
        
        
data_path1='Edge.csv'
data_path2='Node.csv'
graph,edge_capacity,node_capacity,target=process_data(data_path1,data_path2)
global_edge_capacity=[]
global_node_capacity=[]
for i in range(1000):
    global_edge_capacity.append(copy.deepcopy(edge_capacity))
    global_node_capacity.append(copy.deepcopy(node_capacity))
result=[]
t=0

while global_node_capacity[t][0]>0:
    #print(global_node_capacity[t][0])
    global_edge_capacity,global_node_capacity=core(target,copy.deepcopy(graph),global_edge_capacity,global_node_capacity,t,result)
    t+=1
    global_node_capacity[t][0]=global_node_capacity[t-1][0]